1. Field of the Invention
This invention relates to high capacity packet switching apparatus, in general and Asynchronous Transfer Mode (ATM) cell switching apparatus, in particular which is typically used for high speed multimedia networking communications. More particularly, this invention is directed towards decentralized and pipeline control based ATM switching apparatus and method to enable high capacity switching.
2. Prior Art
Besides its best possible delay-throughput performance, ATM switching systems employing shared buffers have also been known in the art to incur the lowest cell-loss rate compared to that of the ATM switches employing input or output buffering strategies. However, a typical design of a large shared-buffer based ATM switching system has been severely restricted by the bottleneck created by high memory bandwidth requirements, segregation of the buffer space and centralized buffer control bottleneck which causes the switch performance to degrade as the switch grows in size. In order to preserve its ability to provide for the low cell-loss rate for a given buffer size, an ATM switching network design should attempt to provide for global buffer sharing among all its inputs and output lines, provide memory sharing schemes to allow fair sharing of a common memory space under different traffic type and alleviate performance bottleneck caused by centralized control.
A traditional approach to design a large size shared-buffer based ATM switching systems has been to first design a feasible size shared-buffer ATM switching modules and then interconnect plurality of such modules in some fashion to build a large size switching system. Some of the previously used methods and schemes to build large size shared-buffer based ATM switch can be categorized as follows:
The Multistage Interconnection Network (MIN) approach: According to this general scheme, a multistage interconnection network is used to build a large size shared-buffer based switching system with a small size, shared-buffer switching elements deployed at each node of the interconnection network [SAKURAI Y., et al, "Large-Scale ATM Multistage Switching Network with Shared Buffer Memory Switches," IEEE Communication, January 1991.]. This general scheme of switch growth is known to cause degradation in performance of a shared-buffer architecture as the switch grows in size. Degradation in cell-loss and throughput performance result mainly from internal link conflicts, output blocking and incomplete buffer sharing due to separation of memory space among plurality of modules. Furthermore, it is obvious that this approach does not allow global sharing of the employed buffer space among all of its input-output ports. Because of separation of buffer space, not all output lines can share the entire buffer space of the switch. Under unbalanced traffic it is possible for some switch buffers to overflow while other switch buffers being under utilized.
Growable switch approach [ENG K. Y. et al, "A Growable Packet (ATM) Switch Architecture: Design, Principles and Applications," IEEE Transactions on Communications, February 1992]: Unlike the Multistage Interconnection network approach mentioned above, in growable switch approach, a plurality of shared-buffer based switches are organized in a single stage preceded by a bufferless [N.times.(m/n)N]interconnection network. Although this approach succeeds in providing an improved overall performance, compared to the general MIN approach, it does not allow global sharing of memory space among all its inputs and outputs. It is known in the art that this scheme does not provide best buffer-utilization as it is possible for a buffer belonging to a group of output ports to overflow under unbalanced or bursty traffic conditions while other buffers belonging to other output ports being empty.
The Multiple Shared Memory (MSM) approach [WEI S.X. et al, "On the Multiple Memory Module Approach to ATM Switching," IEEE INFOCOM, 1992]: Unlike the previous two approaches mentioned above, this approach allows for the global sharing of the employed buffer space. However, MSM switch approach employ centralized control of the switching system consisting of plurality of memory modules. Use of centralized control can become a performance bottleneck if the switch grows in size. Furthermore, in MSM switch approach, the conditions for the best possible delay-throughput performance has been derived under the assumption of infinite buffer space in the switching system. In reality, a buffer space tends to be finite and a realistic switching algorithm must accommodate for the constraints imposed by the finiteness of the buffer space in an ATM switching system. A finite buffer space results into cell-loss, and in the absence of an appropriate buffer sharing scheme, it results into performance degradation [KAMOUN F. and KLEINROCK L., "Analysis of Shared Finite Storage in a Computer Network Node Environment Under General Traffic Conditions," IEEE Transactions on Communications, July 1980]. A switching scheme which provides for a global sharing of the buffer space may not necessarily provide for best possible delay-throughput performance if the shared-buffer space tends to be finite. In order to provide for best possible performance with a finite common buffer space, a switching scheme should also be able to enforce various buffer sharing schemes to provide fair sharing of finite buffer space under various traffic types.
In [OSHIMA et al., "A New ATM Switch Architecture based on STS-Type Shared Buffering and Its Implementation," ISS 1992], the proposed shared multibuffer (SMB) based ATM switch design also provide a complete sharing of memory space among all its input and output ports. The shared multibuffer based ATM switch is also disclosed in recently assigned U.S. Pat. No. 5,649,217 to Yamanaka et al. The shared multibuffer switch of Yamanaka et al., schematically shown in FIG. 1, uses a centralized controller to centrally control and manage a plurality of buffers and its write and read operations for each incoming and outgoing cells, centrally manage and update a plurality of address queues for each incoming and outgoing cells, centrally provide instructions to incoming and outgoing spatial switch on how to provide routing of ATM cells corresponding to each of the input and output lines, and centrally coordinate the operation of its various components to realize overall switching function of the switching apparatus. The disadvantage of this approach is that the use of centralized controller can become a performance bottleneck as the switch grows in size (i.e. the input and output lines increase in number and/or speed). Growth in the size of the switch and hence the number of input and output lines would require the centralized controller to perform increased number of tasks (such as write and read operations for ATM cells, storage and management of information in address queues in the central controller) for increased number of memory modules and input/output lines in a fixed switching time-slot. Similarly, as the switch grows in size, the central controller will need to provide increased number of routing instructions to incoming line spatial switch and outgoing line spatial switch for increased number of input and output lines in a fixed switching time-slot. Overall, the centralized controller will have to do increased number of all centralized control functions and memory operations described therein, in a fixed switching time-slot (which is usually smaller than the interarrival time of two consecutive cells). It is obvious that the centralized controller used by Yamanaka et al., as disclosed in U.S. Pat. No. 5,649,217 can easily become a bottleneck to the switch performance as the switch grows in size or switching capacity.